'''
有向图，无向图，带权
    邻接矩阵建图: n*n 矩阵，适合顶点数量少
    邻接表建图： n+e 动态数组(他所有的边)：适合边少
'''
from typing import List, Tuple


def build_digraph_adjacency_matrix(num_vertices, edges) -> List[List[int]]:
    # 邻接矩阵建 有向图
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for u, v in edges:
        matrix[u][v] = 1
    return matrix


def build_undigraph_adjacency_matrix(num_vertices, edges) -> List[List[int]]:
    # 邻接矩阵建 无向图
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1
    return matrix


def build_digraph_adjacency_matrix_with_weight(num_vertices, edges) -> List[List[int]]:
    # 邻接矩阵建 有向有权图
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for u, v, w in edges:
        matrix[u][v] = w
    return matrix


def build_undigraph_adjacency_matrix_with_weight(num_vertices, edges) -> List[List[int]]:
    # 邻接矩阵建 无向有权图
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for u, v, w in edges:
        matrix[u][v] = w
        matrix[v][u] = w
    return matrix


def build_digraph_adjacency_matrix2(num_vertices, edges) -> List[List[int]]:
    # 邻接表建 有向图
    table = [[] for _ in range(num_vertices)]
    for u, v in edges:
        table[u].append(v)
    return table


def build_undigraph_adjacency_matrix2(num_vertices, edges) -> List[List[int]]:
    # 邻接表建 无向图
    table = [[] for _ in range(num_vertices)]
    for u, v in edges:
        table[u].append(v)
        table[v].append(u)
    return table


def build_digraph_adjacency_matrix_with_weight2(num_vertices, edges) -> List[List[Tuple[int, int]]]:
    # 邻接表建 有向有权图
    table = [[] for _ in range(num_vertices)]
    for u, v, w in edges:
        table[u].append((v, w))
    return table


def build_undigraph_adjacency_matrix_with_weight2(num_vertices, edges) -> List[List[Tuple[int, int]]]:
    # 邻接表建 无向有权图
    table = [[] for _ in range(num_vertices)]
    for u, v, w in edges:
        table[u].append((v, w))
        table[v].append((u, w))
    return table
